#include "stdinc.h" 
#include "newhash.h"
#include "extfunc.h" 
#include "extvab.h" 
#include "dfibHeap.h"
#include "fibHeap.h"
#include "darray.h"


//static CTGinHEAP *ctg4heapArray;
extern int inputLinks(FILE *fp, int insertS,char *line);
//unsigned int traverse(unsigned int node,int *far_count,unsigned int *farpath,
	//int *curr_count,unsigned int *currpath,int *used_count,unsigned int *used,int *max_dist,int *node_dist);
//static int *sub_arr;
//static int sub_counter=0;
int rev_comp (const void * a, const void * b)
{
  return ( *(int*)b - *(int*)a );
}
void potential()
{

	char name[256],*line;
	FILE *fp;

	loadUpdatedEdges(graphfile);

	if(!pes)
		loadPEgrads(graphfile);
	
	sprintf(name,"%s.links",graphfile);
	fp = ckopen(name,"r");
	
	createCntMemManager();
	createCntLookupTable();

	lineLen = 1024;
	line = (char *)ckalloc(lineLen*sizeof(char));

	fgets(line,lineLen,fp);
	line[0] = '\0';
	fprintf(stderr,"[%s]before inputLinks loop.\n",__FUNCTION__);
	for(int i=0;i<gradsCounter;i++){	
          inputLinks(fp,pes[i].insertS,line);
	}
	fprintf(stderr,"[%s]links file loaded.\n",__FUNCTION__);
	//ctg4heapArray=ckalloc(100000*sizeof(CTGinHEAP));
	//unsigned int *farthest_path=ckalloc(1000000*sizeof(unsigned int));
	//int farthest_boarder;
	//STACK *track=createStack(100000,sizeof(unsigned int));
	unsigned int *curr_path=ckalloc(1000000*sizeof(unsigned int));
	int curr_boarder;
	unsigned int *dist=ckalloc(10000000*sizeof(unsigned int));
	//int dist_boarder;
	int *predict=ckalloc(1000000*sizeof(int));
	int pred_count=0;
	int used=0;
	//CONNECT *cnt_stack=ckalloc(10000000*sizeof(CONNECT*));
	//int cnt_count=0;
	for(unsigned int i=1;i<=num_ctg;i++){
		if(contig_array[i].inSubGraph)
			continue;
		if(!contig_array[i].downwardConnect){
			predict[pred_count++]=contig_array[i].length;
			contig_array[i].inSubGraph=1;
			contig_array[getTwinCtg(i)].inSubGraph=1;
			fprintf(stderr,"[%d] traversed %d %d .\n",__LINE__,i,getTwinCtg(i));
			++used;
			continue;
		}
		//depth first traversal
		//farthest_boarder=0;
		curr_boarder=0;
		//used_boarder=0;
		unsigned int max_dist=0;
		//int node_dist=0;
		int len=0;
		//contig_array[i].inSubGraph=1;
		//contig_array[getTwinCtg(i)].inSubGraph=1;
		//if(contig_array[i].downwardConnect){
		//traverse(i,&farthest_boarder,farthest_path,&curr_boarder,curr_path,&used_boarder,used,&max_dist,&node_dist);
		//cnt_stack[0]=contig_array[i].downwardConnect;//put in stack
		//++cnt_count;
		
		contig_array[i].inSubGraph=1;
		contig_array[getTwinCtg(i)].inSubGraph=1;
		fprintf(stderr,"[%d] traversed %d %d .\n",__LINE__,i,getTwinCtg(i));
		++used;
		curr_path[curr_boarder]=i;
		dist[curr_boarder]=0;
		while(curr_boarder>=0){
			int curr_bound=curr_boarder;
			int curr_node=curr_path[curr_boarder--];
			int base_dist=dist[curr_bound];
			CONNECT *curr_cnt=contig_array[curr_node].downwardConnect;
			while(curr_cnt){//push all adjacent connect
				if(curr_cnt->weight<3||contig_array[curr_cnt->contigID].inSubGraph
					||contig_array[getTwinCtg(curr_cnt->contigID)].inSubGraph){
					curr_cnt=curr_cnt->next;
					continue;
				}
				curr_path[++curr_boarder]=curr_cnt->contigID;
				contig_array[curr_cnt->contigID].inSubGraph=1;
				contig_array[getTwinCtg(curr_cnt->contigID)].inSubGraph=1;
				fprintf(stderr,"[%d] traversed %d %d .\n",__LINE__,curr_cnt->contigID,getTwinCtg(curr_cnt->contigID));
				++used;
				dist[curr_boarder]=base_dist+
					curr_cnt->gapLen+contig_array[curr_cnt->contigID].length;
				
				if(dist[curr_boarder]>max_dist)
					max_dist=dist[curr_boarder];
				//fprintf(stderr,"curr_boarder %d node_dist %d max_dist %d \n",curr_boarder,
				//	dist[curr_boarder],max_dist);
				curr_cnt=curr_cnt->next;
			}
			
		}
		len+=max_dist;
		
		//}
		if(contig_array[getTwinCtg(i)].downwardConnect){
			curr_boarder=0;
			curr_path[curr_boarder]=i;
			dist[curr_boarder]=0;
			
			while(curr_boarder>=0){
				int curr_bound=curr_boarder;
				int curr_node=curr_path[curr_boarder--];
				int base_dist=dist[curr_bound];
				CONNECT *curr_cnt=contig_array[curr_node].downwardConnect;
				while(curr_cnt){//push all adjacent connect
					if(curr_cnt->weight<3||contig_array[curr_cnt->contigID].inSubGraph
						||contig_array[getTwinCtg(curr_cnt->contigID)].inSubGraph){
						curr_cnt=curr_cnt->next;
						continue;
					}
					curr_path[++curr_boarder]=curr_cnt->contigID;
					contig_array[curr_cnt->contigID].inSubGraph=1;
					contig_array[getTwinCtg(curr_cnt->contigID)].inSubGraph=1;
					fprintf(stderr,"[%d] traversed %d %d .\n",__LINE__,curr_cnt->contigID,getTwinCtg(curr_cnt->contigID));
					++used;
					dist[curr_boarder]=base_dist+
						curr_cnt->gapLen+contig_array[curr_cnt->contigID].length;
					
					if(dist[curr_boarder]>max_dist)
						max_dist=dist[curr_boarder];
					//fprintf(stderr,"curr_boarder %d node_dist %d max_dist %d \n",curr_boarder,
					//	dist[curr_boarder],max_dist);
					curr_cnt=curr_cnt->next;
				}
				
			}
			len+=max_dist;
		}
		/*int ii;
		for(ii=0;ii<used_boarder;++ii){
			contig_array[used[ii]].inSubGraph=0;
		}*/
		if(len!=0){
			predict[pred_count++]=len;
			fprintf(stderr,"[%s]contig %d effective with length %d.\n",__FUNCTION__,i,len);
		}
		fprintf(stderr,"[%s]contig %d over.\n",__FUNCTION__,i);
		
		
	}

	free((void *)line);
	fclose(fp);
	long long int sum=0;
	for(int i=0;i<pred_count;++i){
		sum+=predict[i];
	}
	long long int half=sum/2;
	printf("sum %lld , half  %lld.\n",sum,half);
	qsort(predict,pred_count,sizeof(int),rev_comp);
	sum=0;
	for(int i=0;i<pred_count;++i){	
		printf("len:\t%d\n",predict[i]);
	}
        int i;
	for(i=0;i<pred_count;++i){
		sum+=predict[i];
		printf("len:\t%d\n",predict[i]);
		if(sum>=half)
			break;
	}
	printf("N50 %d , half %lld.\n",predict[i],half);
	printf("used contig %d",used);
}

/*
unsigned int traverse(unsigned int node,int *far_count,unsigned int *farpath,
	int *curr_count,unsigned int *currpath,int *used_count,unsigned int *used,int *max_dist,int *node_dist){
	unsigned int bal = getTwinCtg(node);
	
	currpath[(*curr_count)++]=node;
	used[(*used_count)++]=node;
	used[(*used_count)++]=bal;
	contig_array[node].inSubGraph=1;
	contig_array[bal].inSubGraph=1;
	
	fprintf(stderr,"farcount %d curr_count %d node_dist %d max_dist %d.\n",*far_count,*curr_count,*node_dist,*max_dist);
	CONNECT *tmp_cnt=contig_array[node].downwardConnect;
	while(tmp_cnt){
		unsigned int ctg,bal_ctg;
		ctg=tmp_cnt->contigID;
		bal_ctg=getTwinCtg(ctg);
		if(contig_array[ctg].inSubGraph||contig_array[bal_ctg].inSubGraph
			||contig_array[ctg].flag||contig_array[bal_ctg].flag){
			tmp_cnt=tmp_cnt->next;
			continue;	
		}
		*node_dist+=(tmp_cnt->gapLen+contig_array[ctg].length);
		if(*node_dist>*max_dist){
			int i;
			for(i=0;i<*curr_count;++i){
				farpath[i]=currpath[i];
			}
			*far_count=*curr_count;
			*max_dist=*node_dist+tmp_cnt->gapLen;
		}
		traverse(tmp_cnt->contigID,far_count,farpath,curr_count,currpath,used_count,used,max_dist,node_dist);
		*node_dist-=(tmp_cnt->gapLen+contig_array[ctg].length);
		tmp_cnt=tmp_cnt->next;
	}
	--(*curr_count);
	
	return 0;
}
*/
